package com.jojo.intermediate.day15_tree;

import com.jojo.elementary.entity.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 103、二叉树的锯齿形层序遍历
 *
 * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。
 * （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 *
 * 示例 1：
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[20,9],[15,7]]
 *
 * 示例 2：
 * 输入：root = [1]
 * 输出：[[1]]
 *
 * 示例 3：
 * 输入：root = []
 * 输出：[]
 */
public class ZigzagOrder {

    /** myCode 层序遍历后，按层数判断是否翻转 */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        List<TreeNode> tree = new ArrayList<>();
        tree.add(root);
        int i = 1;
        while (!tree.isEmpty()){
            //每层的所有数据
            List<Integer> level = new ArrayList<>();
            //临时的每层所有节点
            List<TreeNode> temp = new ArrayList<>();
            for (TreeNode treeNode : tree) {
                level.add(treeNode.val);
                if (treeNode.left != null){
                    temp.add(treeNode.left);
                }
                if (treeNode.right != null){
                    temp.add(treeNode.right);
                }
            }
            if (i % 2 == 0) {
                Collections.reverse(level);
            }
            result.add(level);
            tree = temp;
            i++;
        }
        return result;
    }
}
